import functools
from typing import List


class Solution:
    _MOD = 10 ** 9 + 7

    def __init__(self):
        self.inc = 0
        self.dec = 0
        self.jump = []
        self.cost = []
        self.cache = {}

    def busRapidTransit(self, target: int, inc: int, dec: int, jump: List[int], cost: List[int]) -> int:
        self.inc = inc
        self.dec = dec
        self.jump = jump
        self.cost = cost
        return self.dfs(target) % self._MOD

    @functools.lru_cache(None)
    def dfs(self, target):
        if target == 0:
            return 0
        if target == 1:
            return self.inc
        ans = target * self.inc
        for i in range(len(self.jump)):
            mod = target % self.jump[i]
            if mod != 0:
                lower = mod
                upper = self.jump[i] - mod
                ans = min(ans,
                          lower * self.inc + self.dfs((target - lower) // self.jump[i]) + self.cost[i],
                          upper * self.dec + self.dfs((target + upper) // self.jump[i]) + self.cost[i])
            else:
                ans = min(ans, self.dfs(target // self.jump[i]) + self.cost[i])

        return ans


if __name__ == "__main__":
    # 实例1 : 33
    print(Solution().busRapidTransit(target=31, inc=5, dec=3,
                                     jump=[6], cost=[10]))

    # 实例1 : 26
    print(Solution().busRapidTransit(target=612, inc=4, dec=5,
                                     jump=[3, 6, 8, 11, 5, 10, 4], cost=[4, 7, 6, 3, 7, 6, 4]))

    # 测试用例2/80 : 10953125
    print(Solution().busRapidTransit(target=1000000000, inc=1, dec=1,
                                     jump=[2], cost=[1000000]))
